// #include<iostream>
// using std::cin;
// using std::cout;
// using std::endl;

// namespace sl
// {
//     //节点类
//     template<class K>
//     struct BSTNode
//     {
//         BSTNode(const K& key = K())
//             :_left(nullptr)
//             ,_right(nullptr)
//             ,_key(key)
//         {}

//         BSTNode<K>* _left;
//         BSTNode<K>* _right;
//         K _key;
//     };

//     //BSTree类
//     template<class K>
//     class BSTree
//     {
//     public:
//         typedef BSTNode<K> Node;

//         BSTree() = default;//C++11强制编译器自己生成构造函数，因为写过拷贝构造默认就生不成了
//         // BSTree()
//         //     :_root(nullptr)
//         // {}

//         Node* CopyTree(Node* root)
//         {
//             if(root == nullptr)
//                 return nullptr;

//             Node* copyNode = new Node(root->key);
//             copyNode->_left = CopyTree(root->_left);
//             copyNode->_right = CopyTree(root->_right);

//             return copyNode;
//         }
//         //拷贝构造函数
//         BSTree(const BSTree<K>& t)
//         {
//             _root = CopyTree(t._root);
//         }

//         void swap(BSTree<K>& t)
//         {
//             std::swap(_root, t._root);
//         }
//         //赋值重载
//         BSTree<K>& operator=(BSTree<K> t)
//         {
//             swap(t);
//             return *this;
//         }

//         void DestroyTree(Node* root)
//         {
//             if(root == nullptr)
//                 return;

//             DestroyTree(root->_left);
//             DestroyTree(root->_right);
//             delete root;
//         }
//         //析构
//         ~BSTree()
//         {
//             DestroyTree(_root);
//             _root = nullptr;
//         }

//         bool find(const K& key)
//         {
//             Node* cur = _root;
//             while(cur)
//             {
//                 if(cur->_key < key)
//                     cur = cur->_right;
//                 else if(cur->_key > key)
//                     cur = cur->_left;
//                 else
//                     return true;
//             }
//             return false;
//         }

//         //二叉搜索树默认是不冗余的
//         bool insert(const K& key)
//         {
//             if(_root == nullptr)
//             {
//                 _root = new Node(key);
//                 return true;
//             }

//             Node* parent = nullptr;
//             Node* cur = _root;
//             while(cur)
//             {
//                 if(cur->_key < key)
//                 {
//                     parent = cur;
//                     cur = cur->_right;
//                 }
//                 else if(cur->_key > key)
//                 {
//                     parent = cur;
//                     cur = cur->_left;
//                 }
//                 else
//                 {
//                     return false;//默认是不冗余的
//                 }
//             }
//             cur = new Node(key);
//             if(parent->_key < key)
//             {
//                 parent->_right = cur;
//             }
//             else
//             {
//                 parent->_left = cur;
//             }
//             return true;
//         }

//         //递归版本的
//         bool _findR(Node* root, const K& key)
//         {
//             if(root == nullptr)
//                 return false;

//             if(root->_key < key)
//                 _findR(root->_right, key);
//             else if(root->key > key)
//                 _findR(root->_left, key);
//             else
//                 return true;
//         }
//         bool findR(const K& key)
//         {
//             return _findR(_root, key);
//         }

//         bool _insertR(Node* root, const K& key)
//         {
//             if(root == nullptr)
//             {
//                 root = new Node(key);
//                 return true;
//             }

//             if(root->_key < key)
//             {
//                 _insertR(root->_right, key);
//             }
//             else if(root->key > key)
//             {
//                 _insert(root->_left, key);
//             }
//             else
//             {
//                 return false;
//             }
//         }
//         bool insertR(const K& key)
//         {
//             return _insertR(_root, key);
//         }

//         void prevOrder()
//         {
//             _prevOrder(_root);
//         }
//     private:
//         void _prevOrder(Node* root)
//         {
//             if(root == nullptr)
//                 return;

//             printf("%d ", root->_key);
//             _prevOrder(root->_left);
//             _prevOrder(root->_right);
//         }
//         Node* _root;
//     };
// }

// int main()
// {
//     sl::BSTree<int> bs;
//     bs.insert(1);
//     bs.insert(3);
//     bs.insert(5);
//     bs.insert(7);
//     bs.insert(9);

//     bs.prevOrder();
//     return 0;
// }

// #include<iostream>
// using std::cin;
// using std::cout;
// using std::endl;

// namespace sl
// {
//     //节点类
//     template<class K>
//     struct BSTNode
//     {
//         BSTNode(const K& key = K())
//             :_left(nullptr)
//             ,_right(nullptr)
//             ,_key(key)
//         {}

//         BSTNode<K>* _left;
//         BSTNode<K>* _right;
//         K _key;
//     };

//     //BSTree类
//     template<class K>
//     class BSTree
//     {
//     public:
//         typedef BSTNode<K> Node;
//         BSTree()
//             :_root(nullptr)
//         {}

//         Node* CopyNode(Node* root)
//         {
//             if(root == nu#include<iostream>
// using std::cin;
// using std::cout;
// using std::endl;

// namespace sl
// {
//     //节点类
//     template<class K>
//     struct BSTNode
//     {
//         BSTNode(const K& key = K())
//             :_left(nullptr)
//             ,_right(nullptr)
//             ,_key(key)
//         {}

//         BSTNode<K>* _left;
//         BSTNode<K>* _right;
//         K _key;
//     };

//     //BSTree类
//     template<class K>
//     class BSTree
//     {
//     public:
//         typedef BSTNode<K> Node;
//         BSTree()
//             :_root(nullptr)
//         {}

//         Node* CopyNode(Node* root)
//         {
//             if(root == nullptr)
//                 return nullptr;

//             Node* copyNode = new Node(root->_key);
//             copyNode->_left = CopyNode(root->_left);
//             copyNode->_right = CopyNode(root->_right);

//             return copyNode;
//         }
//         //拷贝构造函数
//         //BSTree<K> t2(t1);
//         BSTree(const BSTree<K>& t)
//         {
//             _root = CopyNode(t._root);
//         }
//         //赋值重载
//         //t1 = t2;
//         BSTree<K>& operator=(BSTree<K> t)
//         {
//             std::swap(_root, t._root);
//             return *this;
//         }

//     private:
//         Node* _root;
//     };
// }

// #include<iostream>
// using std::cin;
// using std::cout;
// using std::endl;

// namespace sl
// {
//     //节点类
//     template<class K>
//     struct BSTNode
//     {
//         BSTNode(const K& key = K())
//             :_left(nullptr)
//             ,_right(nullptr)
//             ,_key(key)
//         {}

//         BSTNode<K>* _left;
//         BSTNode<K>* _right;
//         K _key;
//     };

//     //BSTree类
//     template<class K>
//     class BSTree
//     {
//     public:
//         typedef BSTNode<K> Node;

//         BSTree()
//             :_root(nullptr)
//         {}

//         Node* CopyNode(Node* root)
//         {
//             if(root == nullptr)
//                 return nullptr;

//             Node* copyNode = new Node(root->_key);
//             copyNode->_left = CopyNode(root->_left);
//             copyNode->_right = CopyNode(root->_right);

//             return copyNode;
//         }
//         //拷贝构造
//         //BSTree<K> t2(t1);
//         BSTree(const BSTree<K>& t)
//         {
//             _root = CopyNode(t._root);
//         }

//         //赋值重载
//         BSTree<K>& operator=(BSTree<K> t)
//         {
//             std::swap(_root, t._root);
//             return *this;
//         }

//     private:
//         Node* _root;
//     };
// }

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

namespace sl
{
    //节点类
    template <class K>
    struct BSTNode
    {
        BSTNode(const K &key = K())
            : _left(nullptr), _right(nullptr), _key(key)
        {
        }

        BSTNode<K> *_left;
        BSTNode<K> *_right;
        K _key;
    };

    // BSTree类
    template <class K>
    class BSTree
    {
    public:
        typedef BSTNode<K> Node;

        BSTree()
            : _root(nullptr)
        {
        }

        //拷贝构造
        BSTree(const BSTree<K> &t)
        {
            _root = CopyNode(t._root);
        }

        //赋值重载
        BSTree<K> &operator=(BSTree<K> t)
        {
            std::swap(_root, t._root);
            return *this;
        }

        bool Insert(const K &key)
        {
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }

            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false; //默认是不冗余的
                }
            }
            cur = new Node(key);
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }

            return true;
        }

        bool find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return true;
                }
            }
            return false;
        }

        bool Erase(const K &key)
        {
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                //先找
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //找到了
                    //一个孩子: 左为空 | 右为空
                    //两个孩子: 替换法
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if(cur->_right == nullptr)
                    {
                        if(cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            if(cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    else
                    {
                        //两个孩子
                        
                    }
                }
            }
        }

    private:
        Node *CopyNode(Node *root)
        {
            if (root == nullptr)
                return nullptr;

            Node *copyNode = new Node(root->_key);
            copyNode->_left = CopyNode(root->_left);
            copyNode->_right = CopyNode(root->_right);

            return copyNode;
        }

        Node *_root;
    };
}
